<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<link href="CSS/main.css" rel="stylesheet" type="text/css" />
<link href="CSS/style.css" rel="stylesheet" type="text/css" />
<link href="CSS/Layer.css" rel="stylesheet" type="text/css" />
<title>Dijkstra - hoangvp 2010</title>
</head>

<body>
<script type="text/javascript" src="JS/priority_queue.js"></script>
<script type="text/javascript" src="JS/MathHelpers.js"></script>
<script type="text/javascript" src="JS/DOM.js"></script>
<script type="text/javascript" src="JS/layer.js"></script>
<?php
require_once 'Map.class.php';

$x = new Map("map.txt");
$x->printMap();
$x->generateJSCode();
generateJSDebugCode($DEBUG_);
?>
<script type="text/javascript">
function displayVertex(a){
	document.write(a.x+", "+a.y+" với chi phí = "+a.cost+"<br/>");	
}

function isBetter(a, b){
	return ((a.cost < b.cost) ? BETTER : WORSE);
}

function dijkstra(start, finish){
	var startTime = new Date();	
	var expandCount = 0;
	globalStart = start;
	globalFinish = finish;
	var found  = false;	
	var timeDelay;
	loopsCount = 0;
	if(walkable(start.x, start.y) && walkable(finish.x, finish.y)) {			
		//Init
		map[start.x][start.y].cost = 0;
		queue = new PriorityQueue({cmpFunc : isBetter});
		queue.displayOne = displayVertex;
		var traceMap = new Array();
		for(var i=0; i<m; ++i){				
			traceMap[i] = new Array();
			for(var j=0; j<n; ++j){
				queue.push(map[i][j]);
				map[i][j].status = IN_OPEN_SET;
				traceMap[i][j] = start;
				if(terrain[i][j] == 0){
					setG(i, j, map[i][j].cost);
				}
			}
		}

		//queue.adjust();queue.display();
		
		//Main loop
		while(!queue.isEmpty() && found==false){
			++loopsCount;			
			var t = queue.pop();
			//logDebug("Lấy ("+t.x+", "+t.y+") ra khỏi OPEN!");
			t.status = IN_CLOSED_SET;
			setTimeout('fillRed('+t.x+', '+t.y+');', SPEED*loopsCount);			
			if(nodesEqual(t, finish) == true){
				found = true;
			} else if(t.cost == INFINITY){
				break;
			} else {
				timeDelay = SPEED*loopsCount + DELAY;
				for(var i=startIndex; i<aroundLength; ++i){
					var x = t.x + around[i][0];
					var y = t.y + around[i][1];					
					if(doesPathExist(t.x, t.y, x, y)){																						
						setTimeout('fillYellow('+x+', '+y+');', timeDelay);
						if(map[x][y].cost > map[t.x][t.y].cost + costToMove(t.x, t.y, x, y)  && (map[x][y].status != IN_CLOSED_SET)){
							map[x][y].cost = map[t.x][t.y].cost + costToMove(t.x, t.y, x, y);
							setTimeout('setG('+x+', '+y+', '+map[x][y].cost+');', timeDelay);
							traceMap[x][y] = t;
							++expandCount;
							//logDebug("Đưa "+x + " " + y + " vào tập OPEN với chi phí = " + map[x][y].cost);
						}
					}
				}
				queue.adjust();
			}
		}
	}

	var finishTime = new Date();
	document.getElementById("time").innerHTML = "Thời gian: " + (finishTime.getTime() - startTime.getTime()) + " miligiây";
	document.getElementById("examine").innerHTML = "Tỉ lệ duyệt: " + ((loopsCount*100.0) / (m*n)) + " %";
	document.getElementById("expand").innerHTML = "Tỉ lệ xét: " + ((expandCount*100.0) / (m*n)) + " %";
	
	//Trace path
	tracePath(found, traceMap, loopsCount);	
}

function search(){	
	var f = document.route;
	var fx = f.fromX.value;
	var fy = f.fromY.value;
	var tx = f.toX.value;
	var ty = f.toY.value;
	//alert(fx + " " + fy + "\n" + tx + " " + ty);	
	dijkstra(map[fx][fy], map[tx][ty]);	
}

</script>
<form name="searchFrm">
<input type="button" name="searchBtn" value="Bắt đầu" onclick="searchBtnOnclickFunc(this);" />
<input type="button" value="Mới" onclick="window.location.reload();" /><br/>
<input type="checkbox" name="changeBtn" onclick="changeTerrain(this.checked);" />
<input type="button" name="saveBtn" value="Lưu bản đồ" onclick="save();"/>
</form>
<div id="cost"></div>
<div id="time"></div>
<div id="examine"></div>
<div id="expand"></div>
<div>
<textarea id="log" rows="30" cols="100"></textarea>
</div>
<script type="text/javascript">
document.searchFrm.searchBtn.disabled = false;
document.getElementById("layerBtn").setAttribute("onclick", "showHideDijkstraCost(this);");
</script>
</body>
</html>
